package leetcode.tree;

public class WordDictionary {

    private WordDictionary[] dict;
    private boolean isEnd ;

    public WordDictionary() {
        dict = new WordDictionary[26];
        isEnd = false;
    }

    public void addWord(String word) {
        WordDictionary node = this;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.dict[idx] == null)
                node.dict[idx] = new WordDictionary();
            node = node.dict[idx];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        return searchPrefix(word, 0, this);
    }

    public boolean searchPrefix(String word, int idx, WordDictionary node) {
        if (idx == word.length())
            return node.isEnd;
        char ch = word.charAt(idx);
        if (ch == '.') {
            for (int i = 0; i < 26; i++) {
                if (node.dict[i] != null && searchPrefix(word, idx + 1, node.dict[i])) {
                   return true;
                }
            }
            return false;
        } else {
            int index = ch - 'a';
            if (node.dict[index] == null) return false;
            return searchPrefix(word, idx + 1, node.dict[index]);
        }
    }

    public static void main(String[] args) {

        WordDictionary wordDictionary = new WordDictionary();
        wordDictionary.addWord("bad");
        wordDictionary.addWord("dad");
        wordDictionary.addWord("mad");
        wordDictionary.addWord("pad");
        System.out.println(wordDictionary.searchPrefix("ads", 0, wordDictionary));
        System.out.println(wordDictionary.searchPrefix("dad", 0, wordDictionary));
    }

}
